"""
670. 最大交换 - 贪心算法实现

给定一个非负整数，至多可以交换一次数字中的任意两位，返回能得到的最大值。

贪心策略：
1. 从左到右找到第一个可以被更大数字替换的位置
2. 在该位置右侧找到最大的数字，如果有多个相同最大值，选择最右边的
3. 交换这两个位置的数字
"""

class Solution:
    def maximumSwap(self, num: int) -> int:
        """
        贪心算法实现最大交换
        
        算法思路：
        1. 将数字转换为字符数组便于操作
        2. 从左到右遍历，找到第一个可以被更大数字替换的位置
        3. 在该位置右侧找到最大数字的最右位置
        4. 交换两个位置的数字
        
        时间复杂度：O(n) - n为数字位数
        空间复杂度：O(n) - 存储数字字符数组
        """
        # 转换为字符数组
        digits = list(str(num))
        n = len(digits)
        
        # 记录每个位置右侧的最大数字及其位置
        max_digit_right = [''] * n
        max_pos_right = [-1] * n
        
        # 从右向左填充
        max_digit_right[n-1] = digits[n-1]
        max_pos_right[n-1] = n-1
        
        for i in range(n-2, -1, -1):
            if digits[i] > max_digit_right[i+1]:
                max_digit_right[i] = digits[i]
                max_pos_right[i] = i
            elif digits[i] == max_digit_right[i+1]:
                max_digit_right[i] = digits[i]
                max_pos_right[i] = max_pos_right[i+1]  # 选择更右的位置
            else:
                max_digit_right[i] = max_digit_right[i+1]
                max_pos_right[i] = max_pos_right[i+1]
        
        # 从左到右找第一个可以被替换的位置
        for i in range(n):
            # 如果当前位置的数字小于其右侧的最大数字
            if digits[i] < max_digit_right[i]:
                # 在右侧找到最大数字的最右位置
                max_val = max_digit_right[i]
                swap_pos = -1
                for j in range(n-1, i, -1):
                    if digits[j] == max_val:
                        swap_pos = j
                        break
                
                # 执行交换
                if swap_pos != -1:
                    digits[i], digits[swap_pos] = digits[swap_pos], digits[i]
                    break
        
        return int(''.join(digits))
    
    def maximumSwap_simple(self, num: int) -> int:
        """
        简化版贪心算法
        
        思路：
        1. 对于每个位置，在其右侧找最大的数字
        2. 如果找到更大的数字，交换后返回
        3. 如果有多个相同的最大值，选择最右边的
        """
        digits = list(str(num))
        n = len(digits)
        
        for i in range(n):
            # 在右侧找最大值
            max_val = digits[i]
            max_pos = i
            
            for j in range(i+1, n):
                if digits[j] >= max_val:  # 注意是>=，选择最右边的
                    if digits[j] > max_val:
                        max_val = digits[j]
                        max_pos = j
                    elif digits[j] == max_val and j > max_pos:
                        max_pos = j
            
            # 如果找到更大的数字，交换
            if max_val > digits[i]:
                digits[i], digits[max_pos] = digits[max_pos], digits[i]
                break
        
        return int(''.join(digits))
    
    def maximumSwap_bucket(self, num: int) -> int:
        """
        桶排序优化版本
        
        思路：
        1. 记录每个数字最后出现的位置
        2. 从左到右遍历，对于每个位置找是否有更大的数字在后面
        3. 如果有，交换最大的那个数字的最右位置
        """
        digits = list(str(num))
        
        # 记录每个数字最后出现的位置
        last_pos = {}
        for i, digit in enumerate(digits):
            last_pos[digit] = i
        
        # 从左到右遍历
        for i, digit in enumerate(digits):
            # 从9到当前数字+1，找是否有更大的数字在后面
            for larger_digit in range(9, int(digit), -1):
                larger_digit_str = str(larger_digit)
                if larger_digit_str in last_pos and last_pos[larger_digit_str] > i:
                    # 找到了，交换
                    j = last_pos[larger_digit_str]
                    digits[i], digits[j] = digits[j], digits[i]
                    return int(''.join(digits))
        
        return num

def analyze_number(num: int) -> dict:
    """分析数字的性质"""
    digits = list(str(num))
    n = len(digits)
    
    # 检查是否已经是降序排列
    is_descending = all(digits[i] >= digits[i+1] for i in range(n-1))
    
    # 找到第一个逆序的位置
    first_inversion = -1
    for i in range(n-1):
        if digits[i] < digits[i+1]:
            first_inversion = i
            break
    
    # 统计数字出现次数
    digit_count = {}
    for digit in digits:
        digit_count[digit] = digit_count.get(digit, 0) + 1
    
    # 检查是否有重复数字
    has_duplicates = any(count > 1 for count in digit_count.values())
    
    return {
        "number": num,
        "digits": digits,
        "length": n,
        "is_descending": is_descending,
        "first_inversion": first_inversion,
        "digit_count": digit_count,
        "has_duplicates": has_duplicates,
        "max_digit": max(digits),
        "min_digit": min(digits)
    }

def print_analysis(num: int):
    """打印数字分析结果"""
    analysis = analyze_number(num)
    print(f"\n=== 数字 {num} 分析 ===")
    print(f"数字序列: {' '.join(analysis['digits'])}")
    print(f"位数: {analysis['length']}")
    print(f"是否降序: {analysis['is_descending']}")
    print(f"第一个逆序位置: {analysis['first_inversion']}")
    print(f"最大数字: {analysis['max_digit']}")
    print(f"最小数字: {analysis['min_digit']}")
    print(f"有重复数字: {analysis['has_duplicates']}")
    print(f"数字统计: {analysis['digit_count']}")

# 测试函数
def test_algorithm():
    """测试算法正确性"""
    solution = Solution()
    
    # 测试用例
    test_cases = [
        2736,   # 示例1: 7236
        9973,   # 示例2: 9973 (无需交换)
        1234,   # 递增序列: 4231
        4321,   # 递减序列: 4321 (无需交换)
        1000,   # 有0: 1000 (无法改善)
        10,     # 两位数: 10 (无法改善)
        98368,  # 复杂情况: 98863
        1993,   # 重复数字: 9913
        0,      # 边界情况: 0
        9,      # 单位数: 9
    ]
    
    print("670. 最大交换 - 算法测试")
    print("=" * 50)
    
    for i, num in enumerate(test_cases, 1):
        print(f"\n测试用例 {i}: {num}")
        
        # 三种方法的结果
        result1 = solution.maximumSwap(num)
        result2 = solution.maximumSwap_simple(num)
        result3 = solution.maximumSwap_bucket(num)
        
        print(f"优化贪心法: {result1}")
        print(f"简单贪心法: {result2}")
        print(f"桶排序法: {result3}")
        
        # 检查结果一致性
        consistent = result1 == result2 == result3
        print(f"结果一致: {'✓' if consistent else '✗'}")
        
        if not consistent:
            print("❌ 算法结果不一致！")
        
        # 简单分析
        print_analysis(num)

if __name__ == "__main__":
    test_algorithm()
